/* massey.c
 * 
 * Auteurs : Brice Errandonea, Manuel de Palma
 * 
 * Ce programme prend en entrée un fichier crypté à l'aide d'un LFSR de longueur inférieure ou égale à N,
 * dont on connait les 2N premiers bits, et produit en sortie le fichier clair correspondant.
 * 
 * 
 * 
 * Pour compiler : make
 * Pour exécuter : ./massey nomDuFichierADecrypter clairConnu nomDuFichierACreer
 * 
 * où "monFichier" est le nom du fichier à décrypter
 *    "clairConnu" est une chaine de caractères contenant les 2N premiers bits du fichier en clair (chaque caractère représente 8 bits)
 *    "nomDuFichierACreer" est le nom que vous voulez donner au fichier en clair que le programme va générer
 * 
 * 
 * 
 * Opérations sur les bits :
 * 
 * OU bit à bit :	|
 * XOR bit à bit :	^
 * ET bit à bit :	& 
 * NON bit à bit :	~
 * 
 * a = 00011100
 * Décalage vers la gauche :	b = a << 2	b = 01110000
 * Décalage vers la droite :	c = a >> 4	c = 00000001
 * 
 * lire la valeur du ième bit de a : 	"a & (1<<i)"   Attention : le premier bit (le plus à droite) porte bien le numéro 1 et pas 0
 * mettre à 1 le ième bit de a : 	"a |= (1<<i)"
 * mettre à 0 le ième bit de a : 	"a &= ~(1<<i)"
 * inverser le ième bit de a :		"a ^= (1<<i)"
 *
 * On utilisera plutôt ces opérations :
 * 
 * Si a est un char :
 * 
 * lire la valeur du ième bit de a : 	"(a>>(7-i)) & 1"   Attention : le premier bit (le plus à gauche) porte le numéro 0
 * mettre à 1 le ième bit de a : 	"a |= (1<<(7-i))"
 * mettre à 0 le ième bit de a : 	"a &= ~(1<<(7-i))"
 * inverser le ième bit de a :		"a ^= (1<<(7-i))"
 * 
 * Si a est un uint :
 * 
 * lire la valeur du ième bit de a : 	"(a>>(31-i)) & 1"   Attention : le premier bit (le plus à gauche) porte le numéro 0
 * mettre à 1 le ième bit de a : 	"a |= (1<<(31-i))"
 * mettre à 0 le ième bit de a : 	"a &= ~(1<<(31-i))"
 * inverser le ième bit de a :		"a ^= (1<<(31-i))"
 * 
 * 
 */

#include "LFSR.h"


//--------------------------------------------------MAIN-------------------------------------------------------------

int main(int argc, char** argv)
{
  //Vérification de l'argument
  if (argc != 4) 
  {
    printf("Syntaxe : ./massey nomDuFichierADecrypter clairConnu nomDuFichierACreer\n");
    return 1;
  }    
  
  //Ouverture du fichier à décrypter 
  FILE* fichierCrypte;
  fichierCrypte = fopen(argv[1], "r");
  
  if (fichierCrypte == NULL) 
  {
    printf("Le programme n'a pas pu ouvrir ce fichier. Vérifiez qu'il existe et que vous avez le droit de le lire.\n");
    return 1;
  }
  
  printf("Ouverture du fichier %s\n", argv[1]);
  
  int longueurFichier;
  fseek(fichierCrypte, 0, SEEK_END);
  longueurFichier = ftell(fichierCrypte);
  
  uint* crypte;  
  
  int nbCrypte = NfileStore(crypte, fichierCrypte);
  
  printf("%d\n", ubit(crypte[0], 1));
  
  printf("%s\n", (char*) crypte);
    
  uint* clair = malloc(nbCrypte * sizeof(uint)); 
  uint* cle = malloc(nbCrypte * sizeof(uint));
  printf("clair et cle alloués\n", argv[1]);
  fseek(fichierCrypte, 0, SEEK_SET);
  //fread(texteCrypte, sizeof(char), longueurFichier, fichierCrypte);
  fclose(fichierCrypte); 
  
  //Affichage du fichier crypté 
  printf("Le fichier crypté comporte %d octets :\n", longueurFichier);
  Naffiche(crypte, nbCrypte, longueurFichier * 8);
  printf("\n\n");    
    
  //Calcul des premiers bits de la suite chiffrante (la clé)
  uint* debutClair;
  int lConnu = strlen(argv[2]);  
  int nbConnu = Nstore(debutClair, argv[2]);  //On range les bits du clair connu dans le tableau debutClair
  //lconnu est le nombre d'octets connus et nbconnu est le nombre de uints nécessaires pour les stocker
  
  uint* debutCle = malloc(nbConnu * sizeof(uint)); //
  
  int i;    
  for(i = 0; i < lConnu * 8; i++) 
  {
      if (Nbit(crypte, nbConnu, i) == Nbit(debutClair, nbConnu, i)) setBit(debutCle, nbConnu, i, 0);
      else setBit(debutCle, nbConnu, i, 1);      
  }
  
  
  //Affichage du clair connu
  printf("On connait les %d premiers bits du fichier clair :\n", lConnu * 8); 
  Naffiche(debutClair, nbConnu, lConnu * 8);  
  printf("\n\n");    
  
  //Affichage de la clé
  printf("On calcule donc les %d premiers bits de la suite chiffrante :\n", lConnu * 8);  
  Naffiche(debutClair, nbConnu, lConnu * 8);  
  printf("\n\n");  
  
  
  /* On recherche P(X), le polynôme de rétroaction du LFSR qui a généré la clé.
   * On va ajuster son expression à chaque itération de l'algorithme de Berlekamp-Massey.
   * Q(X) et T(X) sont d'anciennes expressions de P(X), issues d'itérations précédentes.   
   */    
  
  //Initialisation de l'algorithme de Berlekamp-Massey
  int L = 0, m = -1;
  uint *P, *Q, *T;
  
  int lP = (lConnu * 8 / 2 + 1); 
  //lP est la longueur maximale (en bits) du polynôme P que l'on peut déterminer avec l'algorithme de Berlekamp-Massey
  int nbP = lP / 4;
  if (lP % 4 > 0) nbP++;
  //nbP est le nombre maximal de uints nécessaire pour stocker les bits de P.
  
  P = malloc(nbP * sizeof(uint));
  Q = malloc(nbP * sizeof(uint));
  T = malloc(nbP * sizeof(uint));
  
  //P(X) = 1, Q(X) = 1, T(X) = 1
  for (i = 0; i < nbP; i++)
  {
    P[i] = 0;
    Q[i] = 0;
    T[i] = 0;
  }  
  setBit(P, nbP, 0, 1);
  setBit(Q, nbP, 0, 1);
  setBit(T, nbP, 0, 1);
      

  //Algorithme de Berlekamp-Massey
  int d, j;
  for (i = 0; i < lConnu * 8; i++)
  {    
    //Calcul de d
    d = Nbit(debutCle, nbConnu, i);    
    for (j = 1; j < L; j++) d += Nbit(P, nbP, j) * Nbit(debutCle, nbConnu, i-j);
    d = d % 2;
    
    if (d == 1)
    {
      for (j = 0; j < nbP; j++) T[j] = P[j]; //On enregistre l'expression précédente de P(X)      
     
      // Partie en cours de développement
      //P(X) = P(X) + g(X) * X^(i-m)
      for (j = 0; j < 32; j++) if(j-i+m >= 0) 
      {
	int mod = (Nbit(P, nbP, j) + Nbit(Q, nbP, j-i+m)) % 2;	
	setBit(P, nbP, j, mod);	
      }
      
      if (2 * L <= i)
      {
	L = i + 1 - L;
	m = i;
	for (j = 0; j < nbP; j++) Q[j] = T[j]; //Dans ce cas, Q(X) prend l'expression précédente de P(X)
      }      
    }    
  }
  //À l'issue de cette boucle, on connaît le polynôme de rétroaction P(X) et la longueur L du LFSR qui a généré la suite chiffrante
  
  //Affichage de L et de P(X) :
  printf("L = %d\n", L);
  printf("P = ");
  Naffiche(P, nbP, L + 1);
  printf("\n\n");
  
  
  //Fin du programme  
  return 0;
}






